مديريت منابع زماني بر روي گراف مبتني بر واحد پردازنده گرافيكي

چکيده

با رشد شگرف پيچيدگي در سيستم‌هاي امروزي، تکنيک‌هاي سنتي طراحي ديگر قادر به بررسي و مديريت مشکلات طراحي نيستند. يک شيوه براي حل اين مشکل، طراحي سيستم به صورت ماژولار(واحدي) و سلسله مراتبي است. اين کار نيازمند اين است که محدوديت‌هاي در سطح سيستم به موانع و محدوديت‌ها در سطح اجزاء تبديل و تقسيم شوند. از اين عمليات عموما به عنوان مديريت بودجه يا منابع نام برده مي‌شود. مساله‌ مديريت منابع براي محدوديت‌هاي طراحي بسياري از جمله زمان‌بندي و فضا مورد مطالعه قرار گرفته است. به طور خاص بودجه بندي زماني براي اين اجرا مي‌شود که تا حد امکان سرعت اجزا را پايين آورد بدون اينکه محدوديت‌هاي زماني سيستم را زير پا بگذاريم. اجزاي کند شده، مي‌توانند براي ارتقاي فضاي سيستم، اتلاف انرژي يا ديگر معيارهاي کيفيت طراحي بهينه‌سازي شوند.مديريت منابع زماني، در عمليات طراحي مختلفي به کار مي‌رود از جمله: سايز بندي دريچه‌ها و کابل‌ها، و نقشه برداري‌هاي کتابخانه اي. در اين پايان نامه به ارائه يک الگوريتم براي مديريت منابع زماني بر روي گراف مبتني بر واحد پردازشگر گرافيکي مي‌پردازيم.

واژه های کلیدی: مديريت منابع زماني، مدیریت زمان، مدیریت هزینه، گراف منابع زمانی، كم هزينه ترين بيشينه جريان، مديريت منابع زماني بر روي گراف، واحد پردازشگر گرافيكي، بهينه سازي طزاحي.



چکيده1

فصل 1. كليات تحقيق2

1-1. مقدمه3

1-2. ساختار واحد پردازنده گرافيكي4

1-3. مقايسه توانايي‌هاي واحد پردازش گرافيکي با واحد پردازنده مركزي5

1-4. تكنولوژي کودا9

1-5. شناسايي سيستم12

1-6. گراف14

1-6-1.مقدمه14

1-6-2. آشنايي با گراف15

1-6-3. ماتريس وقوع و ماتريس مجاورت15

1-6-4. زيرگراف15

1-6-5. مسيرها16

1-6-6. دورها17

فصل 2. مروري بر تحقيقات انجام شده19

2-1. مقدمه20

2-2. كاربردهاي بودجه بندي در يك گراف20

2-3. كم هزينه‌ترين جريان22

2-3-1.تعريفمسئله و شرايط22

2-4. بيشينه جريان23

2-4-1. تاريخچه23

2-4-2. تعريف24

2-4-3. كاربردهاي مسئله در دنياي واقعي25

2-4-4. الگوريتم‌هاي حل مسئله بيشينه جريان28

فصل 3. روش تحقيق31

3-1. مقدمه32

3-2. تحليل مسئله و مشخص نمودن پيش فرض ها32

3-2-1.تعريف صورت مسئله32

3-2-2.مسئله كوتاه‌ترين مسير33

3-2-3.بيشينه جريان41

3-3. شرح پياده سازي44

3-4.كاربردها49

3-4-1. مسيريابي در شبكه49

3-4-2. شبكه زنجيره‌اي ‌تامين50

3-4-3. انتساب تطابق كم هزينه ترين جريان بهينه در رديابي جريان ذرات50

فصل 4. نتايج54

4-1. اجراهاي كم هزينه ترين بيشينه جريان با ورودي‌ها و گراف‌هاي داراي كمتر از 500 راس55

4-1-1.اجراي اول55

4-1-2.اجراي دوم56

4-1-3.اجراي سوم58

4-1-4.اجراي چهارم60

4-1-5.جراي پنجم62

4-1-6.اجراي ششم62

4-1-7. اجراي هفتم63

4-1-8. اجراي هشتم63

4-1-9. اجراي نهم63

4-1-10. اجراي دهم64

4-1-11. اجراي يازدهم64

4-1-12. اجراي دوازدهم65

4-1-13. اجراي سيزدهم65

4-1-14. اجراي چهاردهم65

4-1-15. اجراي پانزدهم66

4-1-16. اجراي شانزدهم66

4-1-17. اجراي هفدهم67

4-1-18. اجراي هجدهم67

4-1-19. اجراي نوزدهم67

4-1-20. اجراي بيستم68

4-2. نمودارهاي نتايج براي گراف هاي داراي راس هاي كمتر از 50068

4-2-1.پيچيدگي زماني الگوريتم68

4-2-2.زمان اجراي الگوريتم در سيستم اول69

4-2-3.زمان اجراي الگوريتم در سيستم دوم71

4-2-4.مقايسه دو سيستم در گراف هاي كمتر از 500 راس72

4-3. اجراهاي كم هزينه ترين بيشينه جريان با ورودي‌ها و گراف‌هايي داراي بيشتر از 1000 راس73

4-3-1.اجراي اول73

4-3-2.اجراي دوم73

4-3-3.اجراي سوم74

4-3-4.اجراي چهارم74

4-3-5.اجراي پنجم75

4-3-6.اجراي ششم75

4-3-7.اجراي هفتم75

4-3-8. اجراي هشتم76

4-3-9. اجراي نهم76

4-3-10. اجراي دهم77

4-3-11. اجراي يازدهم77

4-3-12. اجراي دوازدهم77

4-3-13. اجراي سيزدهم78

4-3-14. اجراي چهاردهم78

4-3-15. اجراي پانزدهم79

4-3-16. اجراي شانزدهم79

4-4. نمودارهاي نتايج براي گراف هاي داراي راس هاي بيشتر از 100080

4-4-1.زمان اجراي الگوريتم در سيستم اول80

4-4-2.زمان اجراي الگوريتم در سيستم دوم81

4-4-3.مقايسه دو سيستم83

فصل 5. جمع بندی و نتیجه گیری84

5-1. نتيجه85

5-2. نتايج کسب شده از اجراي الگوريتم86

مراجع88

پيوست الف92

پيوست ب94

پرداخت با کلیه کارتهای عضو شتاب امکان پذیر است.